﻿namespace LearnDSTrees;

public class BinarySearchTree
{
    private TreeNode root;

    public BinarySearchTree()
    {
        root = null;
    }

    public void Insert(TreeNode tempRoot, int e)
    {
        TreeNode temp = null;
        while (tempRoot != null)
        {
            temp = tempRoot;
            if (e == tempRoot.element)
            {
                return;
            }
            else if (e < tempRoot.element)
            {
                tempRoot = tempRoot.LeftChild;
            }
            else if (e > tempRoot.element)
            {
                tempRoot = tempRoot.RightChild;
            }
        }

        TreeNode n = new TreeNode(e, null, null);
        if (root != null)
        {
            if (e < temp.element)
            {
                temp.LeftChild = n;
            }
            else
            {
                temp.RightChild = n;
            }
        }
        else
        {
            root = n;
        }
    }

    public TreeNode RecInsert(TreeNode tempRoot, int e)
    {
        if (tempRoot != null)
        {
            if (e < tempRoot.element)
            {
                tempRoot.LeftChild = RecInsert(tempRoot.LeftChild, e);
            }
            else if (e > tempRoot.element)
            {
                tempRoot.RightChild = RecInsert(tempRoot.RightChild, e);
            }
        }
        else
        {
            TreeNode n = new TreeNode(e, null, null);
            tempRoot = n;
        }

        return tempRoot;
    }

    public void InOrder(TreeNode tempRoot)
    {
        if (tempRoot != null)
        {
            InOrder(tempRoot.LeftChild);
            Console.Write(tempRoot.element + " ");
            InOrder(tempRoot.RightChild);
        }
    }

    public void PreOrder(TreeNode tempRoot)
    {
        if (tempRoot != null)
        {
            Console.Write(tempRoot.element + " ");
            PreOrder(tempRoot.LeftChild);
            PreOrder(tempRoot.RightChild);
        }
    }

    public void PostOrder(TreeNode tempRoot)
    {
        if (tempRoot != null)
        {
            PreOrder(tempRoot.LeftChild);
            PreOrder(tempRoot.RightChild);
            Console.Write(tempRoot.element + " ");
        }
    }

    public void LevelOrder(TreeNode tempRoot)
    {
        Queue<TreeNode> q = new Queue<TreeNode>();
        TreeNode t = tempRoot;
        Console.Write(t.element + " ");
        q.Enqueue(t);
        while (q.Count != 0)
        {
            t = (TreeNode)q.Dequeue();
            if (t.LeftChild != null)
            {
                Console.Write(t.LeftChild.element + " ");
                q.Enqueue(t.LeftChild);
            }

            if (t.RightChild != null)
            {
                Console.Write(t.RightChild.element + " ");
                q.Enqueue(t.RightChild);
            }
        }
    }

    public bool Search(int key)
    {
        TreeNode tempRoot = root;
        while (tempRoot != null)
        {
            if (key == tempRoot.element)
            {
                return true;
            }
            else if (key < tempRoot.element)
            {
                tempRoot = tempRoot.LeftChild;
            }
            else if (key > tempRoot.element)
            {
                tempRoot = tempRoot.RightChild;
            }
        }

        return false;
    }

    /// <summary>
    /// 递归查询
    /// </summary>
    /// <param name="tempRoot"></param>
    /// <param name="key"></param>
    /// <returns></returns>
    public bool RecSearch(TreeNode tempRoot, int key)
    {
        if (tempRoot != null)
        {
            if (key == tempRoot.element)
                return true;
            else if (key < tempRoot.element)
            {
                return RecSearch(tempRoot.LeftChild, key);
            }
            else if (key > tempRoot.element)
            {
                return RecSearch(tempRoot.RightChild, key);
            }
        }

        return false;
    }

    public bool Delete(int e)
    {
        TreeNode p = root;
        TreeNode pp = null;
        while (p != null && p.element < e)
        {
            pp = p;
            if (e < p.element)
                p = p.LeftChild;
            else
            {
                p = p.RightChild;
            }
        }

        if (p == null)
            return false;
        if (p.LeftChild != null && p.RightChild != null)
        {
            TreeNode s = p.LeftChild;
            TreeNode ps = p;
            while (s.RightChild != null)
            {
                ps = s;
                s = s.RightChild;
            }

            p.element = s.element;
            p = s;
            pp = ps;
        }

        TreeNode c = null;
        if (p.LeftChild != null)
        {
            c = p.LeftChild;
        }
        else
        {
            c = p.RightChild;
        }

        if (p == root)
        {
            root = null;
        }
        else
        {
            if (p == pp.LeftChild)
            {
                pp.LeftChild = c;
            }
            else
            {
                pp.RightChild = c;
            }
        }

        return true;
    }

    public int CountNumberOfNodes(TreeNode root)
    {
        if (root != null)
        {
            int x = CountNumberOfNodes(root.LeftChild);
            int y = CountNumberOfNodes(root.RightChild);
            return x + y + 1;
        }

        return 0;
    }

    public int TreeHeight(TreeNode root)
    {
        if (root != null)
        {
            int x = TreeHeight(root.LeftChild);
            int y = TreeHeight(root.RightChild);
            return Math.Max(x, y) + 1;
        }

        return 0;
    }
}